package outoforder.leetcode;


import java.util.HashMap;

/**
 * @author shhjiang_001
 * @create 2020-07-07 23:03
 */
public class Solution337 {
    public int rob1(TreeNode root) {
        int dp_0 = 0;
        int dp_1 = 0;
        int res = method(dp_0,dp_1,root);
        return res;
    }

    private int method(int dp_0, int dp_1, TreeNode root) {
        int temp = dp_0;
        dp_0 = Math.max(temp,dp_1);
        dp_1 = temp+root.val;
        int leVal = 0;
        int riVal = 0;
        if (root.left != null){
            leVal = method(dp_0,dp_1,root.left);
        }
        if (root.right != null){
             riVal = method(dp_0,dp_1,root.right);
        }
        if (root.left == null && root.right == null){
            leVal = Math.max(dp_0,dp_1);
        }
        return leVal+riVal;
    }
    HashMap<TreeNode, Integer> map = new HashMap<>();
    public int rob2(TreeNode root) {
        if (root == null) return 0;
        if (map.containsKey(root)){
            return map.get(root);
        }
        int do_it = root.val+ (root.left==null?0:rob2(root.left.left)+rob2(root.left.right))+(root.right==null?0:rob2(root.right.left)+rob2(root.right.right));
        int not_do = rob2(root.left)+rob2(root.right);
        int res = Math.max(do_it,not_do);
        map.put(root,res);
        return res;
    }

    // 递归
    public int rob(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0],res[1]);
    }

    private int[] dp(TreeNode root) {
        if (root==null) return new int[]{0,0};
        int[] left = dp(root.left);
        int[] right = dp(root.right);
        int rob = root.val + left[0] + right[0];
        int not_rob = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{not_rob,rob};
    }

}
